Giải thuật tham lam

Trong giải thuật tham lam giải bài toán xây dựng cây mã tiền tố tối ưu của Huffman, ở mỗi bước ta chọn hai chữ cái có tần số thấp nhất để mã hóa bằng từ mã dài nhất.Giả sử có tập A gồm n {\displaystyle n} ký hiệu và hàm trọng số tương ứng W ( i ) , i = 1.. n {\displaystyle W(i),i=1..n} .

• Khởi tạo: Tạo một rừng gồm n cây, mỗi cây chỉ có một nút gốc, mỗi nút gốc tương ứng với một ký tự và có trọng số là tần số/tần suất của ký tự đó W ( i ) {\displaystyle W(i)} .
• Lặp:
  • Mỗi bước sau thực hiện cho đến khi rừng chỉ còn một cây:
  • Chọn hai cây có trọng số ở gốc nhỏ nhất hợp thành một cây bằng cách thêm một gốc mới nối với hai gốc đã chọn. Trọng số của gốc mới bằng tổng trọng số của hai gốc tạo thành nó.

Như vậy ở mỗi bước số cây bớt đi một. Khi rừng chỉ còn một cây thì cây đó biểu diễn mã tiền tố tối ưu với các ký tự đặt ở các lá tương ứng.